#define DEBUG
#include <cstdio>

using namespace std;

const long long mods=1004535809;

int getFa(int *set, int o) {
  return set[o]==o ? o : (set[o]=getFa(set, set[o]));
}

long long solve(int o, int n, int side[][2]) {
  static bool book[100];
  if (o<=side[0][0]) {
    long long ret=solve(o+1, n, side);
    book[o]=true;
    ret = (solve(o+1, n, side)+ret)%mods;
    book[o]=false;
    return ret;
  } else {
    static int set[130000];
    for (int i=1; i<=n; i++) {
      set[i]=i;
    }

    for (int i=1; i<=side[0][0]; i++) {
      if (book[i]) {
	if (getFa(set, side[i][0])!=getFa(set, side[i][1])) {
	  set[getFa(set, side[i][0])] = getFa(set, side[i][1]);
	}
      }
    }
    for (int i=2; i<=n; i++) {
      if (getFa(set, i)!=getFa(set, i-1)) {
	return 0;
      }
    }
    return 1;
  }
}

int main() {
#ifdef DEBUG
  freopen("2.in", "r", stdin);
  freopen("2.out", "w", stdout);
#endif

  static int side[100][2];
  int n;
  scanf("%d", &n);
  for (int i=1; i<=n; i++) {
    for (int j=i+1; j<=n; j++) {
      side[++side[0][0]][0]=i;
      side[side[0][0]][1]=j;
    }
  }

  printf("%lld", n>1 ? solve(1, n, side) : 1);

  fclose(stdin);
  fclose(stdout);
  return 0;
}
